#include <iostream>

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        if (n == 3)
            return 3;

        vector<int> dp = {1, 2, 3};
        for (int i = 4; i <= n; i++) {
            int tmp = dp[dp.size() - 1] + dp[dp.size() - 2];
            dp.push_back(tmp);
        }
        return dp.back();
    }
};

bool test01() {
    Solution solution;
    int n = 1;
    int result = solution.climbStairs(n);
    int expected = 1;
    std::cout << "输入：" << n << std::endl;
    std::cout << "输出：" << result << std::endl;
    std::cout << "预期结果：" << expected << std::endl;
    bool pass = (result == expected);
    std::cout << "测试" << (pass ? "通过" : "失败") << std::endl;
    return pass;
}

bool test02() {
    Solution solution;
    int n = 2;
    int result = solution.climbStairs(n);
    int expected = 2;
    std::cout << "输入：" << n << std::endl;
    std::cout << "输出：" << result << std::endl;
    std::cout << "预期结果：" << expected << std::endl;
    bool pass = (result == expected);
    std::cout << "测试" << (pass ? "通过" : "失败") << std::endl;
    return pass;
}

bool test03() {
    Solution solution;
    int n = 3;
    int result = solution.climbStairs(n);
    int expected = 3;
    std::cout << "输入：" << n << std::endl;
    std::cout << "输出：" << result << std::endl;
    std::cout << "预期结果：" << expected << std::endl;
    bool pass = (result == expected);
    std::cout << "测试" << (pass ? "通过" : "失败") << std::endl;
    return pass;
}

bool test04() {
    Solution solution;
    int n = 4;
    int result = solution.climbStairs(n);
    int expected = 5;
    std::cout << "输入：" << n << std::endl;
    std::cout << "输出：" << result << std::endl;
    std::cout << "预期结果：" << expected << std::endl;
    bool pass = (result == expected);
    std::cout << "测试" << (pass ? "通过" : "失败") << std::endl;
    return pass;
}

bool test06() {
    Solution solution;
    int n = 6;
    int result = solution.climbStairs(n);
    int expected = 13;
    std::cout << "输入：" << n << std::endl;
    std::cout << "输出：" << result << std::endl;
    std::cout << "预期结果：" << expected << std::endl;
    bool pass = (result == expected);
    std::cout << "测试" << (pass ? "通过" : "失败") << std::endl;
    return pass;
}


int main() {
    std::cout << "this is Leetcode-70-demo." << std::endl;
    std::cout << "test01:" << std::endl;
    int total = 0, passed = 0;
    total++; if (test01()) passed++;

    std::cout << "test02:" << std::endl;
    total++; if (test02()) passed++;

    std::cout << "test03:" << std::endl;
    total++; if (test03()) passed++;

    std::cout << "test04:" << std::endl;
    total++; if (test04()) passed++;

    std::cout << "test06:" << std::endl;
    total++; if (test06()) passed++;
    std::cout << "\n通过用例：" << passed << "/" << total
              << "，通过率：" << (total ? (passed * 100 / total) : 0) << "%" << std::endl;
    return 0;
}
